#Problem 18

import unittest
import functools as ft
import itertools as it

trianglestring = '''
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23'''

def number_triangle(string):
	t = []
	for line in string.split('\n'):
		if line:
			t.append(list(map(int, line.split())))
	return t


'''
la soluzione ottima.. backwords method. si parte dal basso
ogni due righe possiamo vederle come:

a b x x x
c x x x x x

se il percorso ottimo finisce in c, pensando solo agli ultimi due passaggi
c può essere o (c+a) o (c+b)
così.. per ogni elemento della gida di c e per ogni elemento della riga di ab..
(fino all'inizio del triangolo)
tornando alla fine del triangolo, la soluzione ottima, fra le due candidate [(c+a) (c+b)] ..
qual'è? max( [c+a, c+b] ).

ricapitolando, si parte dal basso (triangolo rovesciato)
con la riga di c (riga corrente) e la riga di ab (riga precedente)
si risale sostituendo alla riga di ab
una riga che contiene i massimi fra tutti i possibili abc
'''

def sum_rows(pre,current):
	#print("pre:{0} current{1}".format(pre,current))
	a, b = 0, 0
	for i,c in enumerate(current):
		if i<len(pre): a = pre[i]
		if i<len(pre)-1: b = pre[i+1]
		current[i] = (c+a, c+b)
	#print("after for, current:"+str(current))
	current = list(map(max, current))
	return current

ts = '''
3
7 4
2 4 6
8 5 9 3'''

def maxsumpath(triangle):
	return ft.reduce(sum_rows, triangle)

print("-------- ts")
t = number_triangle(ts)[::-1]
for line in t: print(line)
print("ts maxpath: {0}".format(maxsumpath(t)))
print("--------- ti")
ti = number_triangle(trianglestring)[::-1]
for line in ti: print(line)
print("ti maxpath: {0}".format(maxsumpath(ti)))

def maxpath(triangle):
	# this solution is a greedy one: local best get to toal best-
	# this is not a good problem for greedy solutions. fuckoff
	path = [triangle[0][0]]
	index = 0
	preline = triangle[0]
	for line in triangle[1:]:
		ns = line[index:index+2]
		if ns[0]>ns[1]:
			imax = index
		else: imax = index+1
		path.append(line[imax])
		index = imax
	return path


		

class Test(unittest.TestCase):
	def test_triangle(self):
		t = '''
1
1 2
1 2 3'''
		tl = [[1], [1, 2], [1, 2, 3]]
		self.assertEqual(number_triangle(t), tl)

	def test_max_path(self):
		t = '''
3
7 4
2 4 6
8 5 9 3'''
		tp = [3,7,4,9]
		
		path = maxpath(number_triangle(t))
		print("{0} {1}".format(path, sum(path)))
		self.assertEqual(path, tp)
		self.assertEqual(sum(path), 23)

	def test_euler18(self):
		t = trianglestring
		t = number_triangle(t)
		path = maxpath(t)
		print(path)
		print(sum(path)) 

#unittest.main()
